package practice;

/**
 * @program: leetcode
 * @description: 快排
 * @author: za2599@gmail.com
 * @create: 2022-06-30 22:33
 **/
public class L0912 {

    /**
     * 列表大小等于或小于该大小，将优先于 quickSort 使用插入排序
     */
    private static final int INSERTION_SORT_THRESHOLD = 7;

    private static final java.util.Random RANDOM = new java.util.Random();

    /**
     * 对数组 nums 的子区间 [left, right] 使用插入排序
     *
     * @param nums  给定数组
     * @param left  左边界，能取到
     * @param right 右边界，能取到
     */
    private void insertionSort(int[] nums, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = nums[i];
            int j = i;
            while (j > left && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
    }

    private void swap(int aOffset, int bOffset, int[] nums) {
        int temp = nums[aOffset];
        nums[aOffset] = nums[bOffset];
        nums[bOffset] = temp;
    }

    public int[] sortArray(int[] nums) {
        // 异常处理
        if(null==nums || nums.length<1) {
            return nums;
        }

        quickSort(0, nums.length-1, nums);
        return nums;
    }

    private void quickSort(int left, int right, int[] nums) {
        if(left>=right) {
            return;
        }

        if((right-left)<INSERTION_SORT_THRESHOLD) {
           insertionSort(nums, left, right);
           return;
        }

        int randomIndex = left + RANDOM.nextInt(right - left + 1);
        swap(randomIndex, left, nums);

        int pivotLeft = left;
        int pivotRight = right+1;

        // 基准数取值
        int pivot = nums[left];

        while(true) {

            while (pivotLeft<right && nums[++pivotLeft]<pivot) {}


            // 注意，这里必须用left，千万不能用pivotLeft，
            // 假设只有两个值[2,3]，如果用pivotLeft，
            // 此时pivotLeft已经在前面的步骤中从0变成了1，
            // 那么pivotRight就没有机会自减了，
            // 那么在循环外面的swap，就是swap(0,1,nums)，
            // 那么[2,3]就变成了[3,2]
            while (pivotRight>left && nums[--pivotRight]>pivot) {}

            // 如果左右指针已经碰头，就在此退出循环
            if (pivotLeft>=pivotRight) {
                break;
            }

            // 把基准值放在中间
            swap(pivotLeft, pivotRight, nums);
        }

        // 注意，一定要用pivotRight，
        // 像[2,3]这样的数组，pivotRight在此等于0，pivotLeft在此等于1，
        // 一旦用pivotLeft，下面的操作就会把[2,3]变成[3,2]
        swap(left, pivotRight, nums);

        // 基准数位置左边的数组做一次快排
        quickSort(left, pivotRight-1, nums);
        // 基准数位置右边的数组做一次快排
        quickSort(pivotRight+1, right, nums);
    }


    public static void main(String[] args) {
        Tools.print(new L0912().sortArray(new int[] {
                        -7087,
                12694,
                -19352,
                -7660,
                12052,
                -11316,
                -352,
                18321,
                15,
                19967,
                6331,
                -1289,
                6540,
                -10454,
                -19309,
                -10193,
                15074,
                8926,
                510,
                -11044,
                5156,
                10397,
                18477,
                7011,
                -16822,
                -8281,
                -13675,
                -14616,
                11103,
                -3338,
                1597,
                -10313,
                15808,
                16242,
                11438,
                19029,
                -3969,
                -5137,
                6955,
                -11426,
                11283,
                -9429,
                15512,
                5109,
                -16951,
                9741,
                7024,
                7374,
                -1429,
                -3822,
                16494,
                11183,
                13581,
                -624,
                -8692,
                9033,
                13253,
                -6781,
                -8030,
                -12564,
                -6495,
                -8075,
                6375,
                -7638,
                -8894,
                -15126,
                6196,
                7565,
                -8335,
                17298,
                15965,
                -10424,
                -11440,
                115,
                -15303,
                -8185,
                -14136,
                -4704,
                5078,
                19498,
                -8636,
                19068,
                1950,
                1980,
                -19147,
                1634,
                -634,
                5704,
                -16161,
                -19512,
                18818,
                1598,
                -13237,
                -4924,
                8819,
                -17508,
                -6143,
                -922,
                -1262,
                5676,
                -7286,
                19153,
                17772,
                12016,
                7017,
                -3883,
                10757,
                -5870,
                -4128,
                17396,
                17387,
                14927,
                11939,
                19301,
                13760,
                16166,
                15332,
                10975,
                -5162,
                -19353,
                9945,
                -295,
                -13588,
                -1908,
                -13244,
                -348,
                -12064,
                10565,
                913,
                -16781,
                16214,
                -1846,
                7727,
                5283,
                10492,
                -2839,
                15925,
                -7995,
                12903,
                -9995,
                -9204,
                -15275,
                -9845,
                -3452,
                19892,
                -1347,
                -3371,
                11224,
                -14823,
                -12338,
                -19412,
                -516,
                -14527,
                6209,
                11369,
                12343,
                18372,
                11136,
                -8844,
                15963,
                12194,
                12863,
                352,
                -3911,
                932,
                19855,
                -1760,
                1582,
                3047,
                19942,
                15541,
                -9546,
                10888,
                -19901,
                2208,
                13005,
                6209,
                -11636,
                -9385,
                -14842,
                3135,
                14370,
                -1867,
                4359,
                11118,
                14559,
                -11432,
                8041,
                -17623,
                -8234,
                8526,
                -3630,
                -2328,
                -5249,
                6459,
                -1228,
                15233,
                9079,
                1967,
                -7570,
                -10208,
                -4607,
                -18786,
                -8133,
                -2689,
                -10510,
                -8290,
                5871,
                4110,
                19997,
                -15373,
                -3223,
                15082,
                31,
                16580,
                19445,
                -8625,
                -13902,
                563,
                18675,
                -8786,
                -10333,
                16538,
                -10187,
                8547,
                9519,
                -6153,
                3882,
                5856,
                8888,
                -3421,
                -5138,
                854,
                2753,
                -4262,
                9691,
                5063,
                14578,
                -7848,
                -5054,
                -15810,
                -18044,
                12625,
                -14412,
                3328,
                -566,
                -19445,
                11381,
                3560,
                -5192,
                -6656,
                -7173,
                -15055,
                12891,
                9686,
                -19568,
                18826,
                10318,
                1468,
                -16674,
                -16909,
                15291,
                17799,
                5046,
                10612,
                19375,
                17086,
                -10253,
                15491,
                -6985,
                -4277,
                -16787,
                -16594,
                11732,
                -14766,
                -5306,
                11835,
                -18847,
                -10274,
                2856,
                5419,
                5852,
                14133,
                -3833,
                -13140,
                1620,
                10796,
                10005,
                6078,
                9813,
                15761,
                -14294,
                983,
                -13258,
                13076,
                1608,
                -1741,
                8267,
                -12633,
                10641,
                15283,
                17260,
                15384,
                -1784,
                12756,
                -7642,
                18413,
                11414,
                -17334,
                -15308,
                15784,
                -312,
                609,
                -11931,
                -7313,
                -12871,
                -12530,
                1206,
                -5250,
                12766,
                18211,
                9164,
                -3788,
                -12276,
                -19227,
                6,
                -12363,
                14720,
                -15384,
                -8519,
                -15815,
                -13884,
                -2352,
                10218,
                -11789,
                -5998,
                -9599,
                17076,
                -8880,
                -18821,
                -16235,
                5221,
                7965,
                -12857,
                13865,
                7218,
                -17504,
                -5725,
                743,
                1735,
                -12453,
                1333,
                -19352,
                8745,
                10987,
                -15045,
                -2083,
                13711,
                -12331,
                9407,
                14446,
                8538,
                17810,
                1143,
                -18733,
                10340,
                605,
                12922,
                18915,
                536,
                8409,
                6167,
                16435,
                -10055,
                7554,
                9507,
                -15106,
                12534,
                13059,
                -6382,
                900,
                -2175,
                -1139,
                -14227,
                5575,
                12791,
                -9641,
                9220,
                -8166,
                5816,
                10594,
                19660,
                5069,
                -8561,
                9443,
                -9302,
                -3421,
                -17841,
                2409,
                5116,
                -6415,
                7066,
                14230,
                12,
                -9552,
                10898,
                -10097,
                -19818,
                -13256,
                -16487,
                -11983,
                1789,
                3823,
                -11624,
                -9337,
                -7308,
                1314,
                13718,
                -11968,
                -6123,
                8151,
                -12878,
                10413,
                17771,
                1023,
                16955,
                -18942,
                7558,
                -6061,
                3179,
                -6256,
                -7347,
                -7415,
                -11644,
                12484,
                -3941,
                -7674,
                -14502,
                19686,
                -5104,
                -5867,
                -7560,
                11337,
                14538,
                -16531,
                17245,
                -14487,
                99,
                11925,
                -1037,
                3409,
                10770,
                18593,
                12227,
                3664,
                25,
                14870,
                15167,
                688,
                -4934,
                7135,
                8382,
                -19761,
                -5987,
                15899,
                -5284,
                15005,
                -11621,
                -6469,
                1634,
                15287,
                -2442,
                -17387,
                6614,
                14545,
                11393,
                6167,
                13038,
                6065,
                -16801,
                -3349,
                -19842,
                13903,
                -4557,
                7903,
                -9232,
                7855,
                -14485,
                16301,
                3713,
                -17675,
                -11570,
                -2815,
                -19367,
                3108,
                -2278,
                9157,
                5853,
                -16279,
                -3446,
                3638,
                -2186,
                -9262,
                12883,
                -8415,
                17380,
                4643,
                -12074,
                13422,
                14476,
                3245,
                19152,
                -15663,
                11470,
                14773,
                5380,
                13324,
                -6534,
                -18981,
                15267,
                -4825,
                -14652,
                8218,
                18253,
                1413,
                11048,
                10764,
                -16244,
                16089,
                -17674,
                -10245,
                -15123,
                -3726,
                -16150,
                -5224,
                -7981,
                13190,
                -9982,
                5563,
                9432,
                -9400,
                8817,
                17004,
                -9057,
                1045,
                16767,
                11065,
                -14602,
                -4156,
                -16822,
                -11155,
                -1856,
                2581,
                7314,
                11949,
                -16295,
                -1351,
                -3011,
                4912,
                -7981,
                18368,
                -8307,
                8481,
                12784,
                -1068,
                5601,
                -7088,
                -9201,
                4132,
                282,
                18170,
                -16144,
                16736,
                12122,
                -16138,
                -14004,
                -5277,
                -14955,
                -6716,
                -4146,
                8505,
                14759,
                5682,
                -11855,
                -6740,
                -11916,
                15756,
                19561,
                -1234,
                -16565,
                10428,
                -13472,
                -1401,
                15549,
                -15929,
                9951,
                -11993,
                -9814,
                5290,
                -18088,
                -5358,
                10303,
                15560,
                -156,
                -3079,
                -14829,
                10476,
                -8946,
                6663,
                994,
                8290,
                12197,
                -14592,
                9857,
                13844,
                17884,
                3182,
                14496,
                -12909,
                9494,
                -5112,
                3294,
                10035,
                8784,
                -13844,
                -2307,
                -5974,
                -12193,
                -7825,
                -11171,
                -14959,
                2920,
                -18460,
                -8188,
                -4611,
                3803,
                16301,
                -6833,
                -14612,
                -17693,
                6023,
                -13814,
                12642,
                17243,
                -19097,
                -2091,
                -1683,
                -19119,
                -14570,
                19422,
                -16219,
                -17702,
                -5763,
                -13763,
                13678,
                -5577,
                5829,
                6431,
                -14134,
                -18064,
                16144,
                -6420,
                -4808,
                -6087,
                -3267,
                6548,
                19595,
                -3091,
                2826,
                4876,
                -16873,
                -4081,
                8651,
                8791,
                -13369,
                13556,
                -17515,
                -6997,
                7150,
                7075,
                -8192,
                -9536,
                2369,
                6351,
                13236,
                -7110,
                7898,
                7115,
                -15394,
                -11876,
                -8618,
                2680,
                1100,
                17947,
                -6188,
                15320,
                4803,
                -2765,
                -3816,
                -7284,
                -16724,
                5952,
                -590,
                1977,
                7282,
                14247,
                -9906,
                18013,
                4797,
                18645,
                1037,
                -18236,
                4876,
                -2250,
                6386,
                -1646,
                8586,
                -18385,
                -13849,
                10046,
                10620,
                -11820,
                8372,
                -7583,
                -198,
                -9411,
                -16637,
                15697,
                -19343,
                -12429,
                -6705,
                19857,
                18528,
                -8393,
                1452,
                4738,
                -2476,
                -7959,
                -13509,
                5959,
                5716,
                11369,
                2565,
                -8890,
                -15231,
                11427,
                4880,
                3860,
                -4834,
                13145,
                5796,
                -15990,
                -9649,
                -11957,
                318,
                -16671,
                5982,
                -8409,
                3566,
                15669,
                2944,
                -19958,
                14248,
                6441,
                7889,
                -16644,
                -192,
                11582,
                11534,
                -10229,
                -14136,
                18303,
                -11306,
                -6568,
                -10566,
                4690,
                3998,
                8380,
                -13356,
                18592,
                4339,
                7663,
                -5999,
                -3077,
                -10648,
                -3650,
                18304,
                4743,
                -19669,
                -17412,
                -1392,
                18795,
                7361,
                -13853,
                5756,
                14195,
                7682,
                -765,
                -7113,
                -15208,
                -19944,
                11828,
                9462,
                -12402,
                7061,
                -52,
                -19182,
                -3537,
                18879,
                -11024,
                -6336,
                -4267,
                -7668,
                19914,
                -19409,
                6779,
                -10995,
                -7896,
                4800,
                -1010,
                -18527,
                16168,
                -19383,
                -7204,
                9276,
                -19597,
                571,
                11996,
                11306,
                -4462,
                2283,
                -15053,
                -19879,
                -5648,
                12621,
                -11756,
                10781,
                6768,
                1847,
                3047,
                15344,
                2566,
                9039,
                -18796,
                -12842,
                -17498,
                -17419,
                8861,
                4705,
                4204,
                432,
                -1170,
                8765,
                -10140,
                12462,
                -12842,
                -18857,
                -13927,
                13366,
                2535,
                12338,
                -18813,
                -8406,
                -4431,
                14040,
                -3332,
                -9935,
                -3923,
                2480,
                12103,
                -16197,
                12760,
                6007,
                5988,
                -19018,
                -11341,
                -16222,
                186,
                6795,
                5506,
                10862,
                3477,
                5352,
                3442,
                19409,
                -3121,
                19960,
                13853,
                -4873,
                1928,
                -9316,
                8799,
                14378,
                11655,
                -9844,
                155,
                12276,
                1125,
                -4522,
                12960,
                -4241,
                5306,
                5061,
                -12379,
                4190,
                17921,
                -7873,
                -12306,
                167,
                -13350,
                15773,
                -8380,
                7374,
                10135,
                -3365,
                14375,
                -18584,
                -4171,
                7991,
                1228,
                2435,
                -887,
                19077,
                5226,
                3461,
                7319,
                -9653,
                -13179,
                16413,
                -15835,
                15464,
                12024,
                -3418,
                765,
                -10208,
                9764,
                -10373,
                -14998,
                4080,
                -13631,
                5969,
                16520,
                3196,
                -2360,
                13947,
                -19472,
                -10407,
                7692,
                -3796,
                -14113,
                -6302,
                2561,
                19235,
                -12780,
                -7360,
                16061,
                172,
                11965,
                -7398,
                7235,
                -12682,
                -4105,
                -7202,
                -13825,
                -6980,
                -11405,
                17747,
                11897,
                6536,
                2362,
                13240,
                -14578,
                19672,
                -9658,
                -13384,
                -15980,
                835,
                -2270,
                -6842,
                7735,
                -17845,
                9228,
                9242,
                -1440,
                -15220,
                10255,
                -19797,
                -6113,
                3602,
                16087,
                -9410,
                7718,
                -15603,
                14941,
                -6208,
                2651,
                -843,
                -3066,
                4264,
                12641,
                -18398,
                -3196,
                -12555,
                -11965,
                -4922,
                10903,
                2935,
                -2204,
                -1400,
                -18538,
                12521,
                -6808,
                -13421,
                -8763,
                -2464,
                -13584,
                -15195,
                17682,
                -6820,
                -7230,
                3233,
                11609,
                -10096,
                19082,
                -621,
                -3669,
                11295,
                250,
                17900,
                -9238,
                10334,
                -10717,
                -739,
                14372,
                6159,
                11931,
                19729,
                -15975,
                -12149,
                1314,
                -11422,
                9986,
                -4376,
                10047,
                9067,
                -15413,
                15588,
                15176,
                537,
                10580,
                -1415,
                -10672,
                10387,
                -9370,
                17150,
                3823,
                10474,
                -14136,
                -7124,
                9004,
                -1054,
                -12769,
                4019,
                -15501,
                2328,
                -15829,
                -4865,
                -17135,
                15209,
                10520,
                936,
                10864,
                464,
                -4992,
                592,
                -10675,
                3079,
                13921,
                8829,
                -9355,
                -11186,
                -4730,
                9296,
                -4196,
                -7400,
                15783,
                14539,
                -18144,
                13275,
                8097,
                12408,
                5863,
                12489,
                10486,
                -9983,
                -9604,
                16030,
                -15590,
                8129,
                6301,
                1512,
                6626,
                -16987,
                3459,
                12449,
                -11829,
                17339,
                -15050,
                -19621,
                -9915,
                13686,
                16805,
                -18241,
                7399,
                -1600,
                16620,
                -9797,
                15788,
                -16809,
                7860,
                -11210,
                -14315,
                8427,
                -11155,
                -8675,
                7561,
                -13509,
                6583,
                1674,
                -4488,
                -16166,
                -10665,
                -14639,
                -13597,
                -18172,
                16511,
                5173,
                13647,
                -13339,
                -5727,
                -9808,
                -4765,
                -15407,
                10270,
                1584,
                -17269,
                -13035,
                18654,
                -6424,
                7741,
                17651,
                -5526,
                2203,
                16282,
                10640,
                2027,
                -2789,
                8476,
                -9863,
                -1687,
                -13960,
                -8498,
                3411,
                -8897,
                -2749,
                16012,
                4830,
                10011,
                13377,
                7906,
                9357,
                -4430,
                15510,
                -5490,
                2660,
                1298,
                -16258,
                -10686,
                -7739,
                -8275,
                11664,
                10767,
                -13537,
                -13153,
                -14408,
                -11957,
                6708,
                10506,
                17915,
                6181,
                9002,
                -18124,
                13944,
                6346,
                -14458,
                19618,
                19587,
                18708,
                -19547,
                -7058,
                11479,
                7240,
                -13794,
                -10672,
                4225,
                -3328,
                1012,
                13988,
                -9021,
                19353,
                -15330,
                -1008,
                -1738,
                18539,
                -15437,
                -9669,
                16289,
                2644,
                15095,
                5536,
                3601,
                301,
                -1452,
                7068,
                1247,
                13544,
                19946,
                5259,
                13558,
                -13024,
                -16496,
                9646,
                5653,
                52,
                12011,
                6472,
                -16349,
                -16135,
                19715,
                -4372,
                -4470,
                19236,
                -8837,
                -5701,
                6024,
                -16243,
                4741,
                -11718,
                14687,
                -8487,
                -10800,
                4121,
                -202,
                -3561,
                19181,
                18345,
                2541,
                19268,
                -3175,
                4216,
                -9135,
                -16489,
                -1101,
                6829,
                -7817,
                13437,
                3405,
                10591,
                8191,
                -9523,
                12491,
                6098,
                -2887,
                -12956,
                7651,
                -224,
                7974,
                -6348,
                11323,
                7219,
                1104,
                6556,
                8154,
                6975,
                10492,
                -19501,
                -8976,
                -16543,
                16768,
                17906,
                -18761,
                -9382,
                6577,
                11298,
                16807,
                16990,
                -7284,
                -5139,
                -15003,
                -1919,
                -334,
                7015,
                7720,
                1165,
                19995,
                -12110,
                -6248,
                7589,
                -2554,
                -6337,
                -17214,
                11815,
                1922,
                10622,
                -16358,
                368,
                -8367,
                9555,
                -9258,
                -9575,
                -17972,
                -15961,
                16078,
                -19732,
                10664,
                8060,
                -11340,
                -14640,
                -15655,
                846,
                -1804,
                2352,
                17072,
                17050,
                -12980,
                -19082,
                -18493,
                11422,
                626,
                -9098,
                19332,
                -365,
                5495,
                -11973,
                16782,
                -14595,
                -2620,
                18718,
                -432,
                -13481,
                -16552,
                14484,
                9943,
                14610,
                -11855,
                -267,
                10665,
                -18611,
                -7205,
                -10225,
                -411,
                12812,
                -10881,
                -11797,
                16338,
                10721,
                14392,
                2014,
                -7382,
                819,
                -7868,
                -15186,
                -11350,
                8261,
                7124,
                19486,
                -12550,
                -4227,
                17901,
                1251,
                -11847,
                -755,
                -11961,
                1900,
                -15831,
                -14017,
                1176,
                15502,
                5104,
                826,
                4953,
                14872,
                -3368,
                8919,
                6016,
                -18033,
                -18489,
                5751,
                4722,
                1075,
                -12055,
                7094,
                12374,
                -1506,
                12710,
                4721,
                3653,
                -10257,
                -7709,
                -2213,
                17398,
                2900,
                -9727,
                15259,
                -3883,
                -6185,
                -15503,
                17846,
                5462,
                18890,
                -31,
                -14183,
                -10346,
                10710,
                12368,
                324,
                3808,
                -3907,
                -1567,
                2286,
                -19945,
                -1077,
                6131,
                11741,
                -15450,
                15066,
                -10562,
                -12270,
                -1751,
                16899,
                374,
                -14688,
                11616,
                7005,
                3793,
                4346,
                -13227,
                -1628,
                5377,
                -14693,
                -15296,
                2535,
                -3358,
                9983,
                8701,
                18499,
                -11393,
                7936,
                -18,
                5006,
                -9393,
                -9609,
                -18689,
                -13326,
                6324,
                3861,
                -18518,
                13685,
                -13858,
                -12961,
                -12645,
                3677,
                -2486,
                8518,
                -3494,
                8301,
                19880,
                -3389,
                -3997,
                -17145,
                7349,
                17967,
                8601,
                -15183,
                -988,
                -9281,
                19443,
                16615,
                6675,
                14079,
                3509,
                -19702,
                3755,
                -12497,
                3230,
                1349,
                15306,
                14350,
                -10152,
                12176,
                -5919,
                17701,
                18663,
                15397,
                -5427,
                1838,
                14336,
                -14874,
                19010,
                18989,
                -17846,
                -1150,
                -15657,
                15885,
                13300,
                16793,
                19556,
                -433,
                -3649,
                3673,
                -7557,
                -4891,
                3426,
                -18437,
                9305,
                -4885,
                -10866,
                13407,
                -13271,
                -12457,
                12227,
                -2622,
                17794,
                -19917,
                12489,
                -10060,
                10388,
                10731,
                11358,
                -10290,
                14406,
                -5847,
                -16052,
                476,
                -15710,
                15548,
                11005,
                11197,
                5598,
                14685,
                -15221,
                -16521,
                -16068,
                -6183,
                12744,
                -10509,
                -18937,
                12606,
                -11077,
                -16262,
                -11012,
                658,
                8816,
                4974,
                14284,
                -19355,
                -5228,
                19487,
                -6166,
                -2824,
                17272,
                -18169,
                4061,
                17802,
                -4919,
                -466,
                9149,
                -385,
                6204,
                -8727,
                14224,
                17779,
                3421,
                10,
                -7109,
                -9290,
                -11524,
                4414,
                -17081,
                16351,
                -18212,
                -3419,
                8669,
                3423,
                -3561,
                -18798,
                -6740,
                18780,
                -4210,
                10134,
                1670,
                17991,
                19402,
                -6506,
                -16193,
                1810,
                -8541,
                12061,
                -12111,
                14453,
                -10012,
                -1027,
                -4969,
                9116,
                -8716,
                18250,
                -18306,
                -4160,
                11222,
                1821,
                9069,
                7004,
                10749,
                7214,
                2158,
                -11785,
                16046,
                -16464,
                -6922,
                12434,
                4389,
                -14720,
                -4724,
                8658,
                18419,
                -18361,
                -11228,
                6488,
                -15265,
                -10562,
                18742,
                19386,
                -14712,
                -15996,
                1171,
                -277,
                11502,
                -3642,
                8381,
                -16760,
                15471,
                7879,
                16433,
                1366,
                -19917,
                4352,
                -4460,
                1499,
                2224,
                15511,
                9322,
                10443,
                -3672,
                17818,
                -19367,
                -7447,
                19654,
                -5174,
                -12125,
                3007,
                -4712,
                14732,
                16938,
                15056,
                -6750,
                12222,
                -9341,
                -2961,
                -9951,
                -17156,
                6080,
                -5633,
                -14206,
                18700,
                18778,
                -15780,
                10493,
                19759,
                3310,
                100,
                14136,
                4071,
                -7522,
                -19915,
                -2981,
                -10707,
                17336,
                17455,
                -13005,
                1147,
                -18767,
                -923,
                -17489,
                19771,
                -19608,
                -7325,
                13668,
                -4537,
                12975,
                -18154,
                2343,
                -7687,
                8735,
                5539,
                1860,
                11944,
                -3560,
                3547,
                9406,
                -16080,
                -19017,
                2966,
                -8109,
                -2968,
                -19872,
                -14222,
                10911,
                8407,
                -12790,
                16114,
                -9451,
                -9540,
                16249,
                -11771,
                -1602,
                17269,
                -18189,
                15400,
                -744,
                3474,
                -7093,
                -2171,
                5737,
                8031,
                -4847,
                11711,
                7312,
                13391,
                12507,
                12445,
                7048,
                3221,
                -14972,
                -8035,
                -16473,
                18653,
                -14384,
                15589,
                -14298,
                -10445,
                -8616,
                7121,
                12319,
                -2490,
                -3298,
                -7897,
                9655,
                -5747,
                -13361,
                7158,
                -186,
                -1217,
                -4141,
                7429,
                -7343,
                -19027,
                -16509,
                7417,
                16235,
                2989,
                -8243,
                17658,
                -10272,
                5795,
                13698,
                -4038,
                -5769,
                -9063,
                7457,
                -10831,
                6927,
                -6065,
                12927,
                -1056,
                -10442,
                -2914,
                -16410,
                19318,
                -14060,
                11791,
                -7633,
                3206,
                7444,
                -14416,
                13159,
                -14023,
                2780,
                17262,
                1374,
                6724,
                -11191,
                7726,
                9671,
                -3618,
                -18229,
                15537,
                -17417,
                6229,
                4083,
                -12816,
                13370,
                4431,
                -6747,
                9541,
                -15584,
                -16374,
                11234,
                1237,
                1842,
                11014,
                -6035,
                8733,
                10095,
                -14317,
                -7209,
                -6325,
                18879,
                -11035,
                2686,
                -19719,
                16754,
                -12793,
                -11803,
                -8497,
                -3346,
                16814,
                7540,
                -10856,
                -8784,
                -12999,
                8128,
                17442,
                18925,
                -11647,
                -16505,
                9644,
                16616,
                -13922,
                17910,
                16671,
                19448,
                -4225,
                -8515,
                -3524,
                11340,
                -9169,
                2693,
                762,
                9350,
                -13948,
                -4173,
                -7536,
                -691,
                -2214,
                1423,
                2368,
                14836,
                9130,
                -19476,
                -1879,
                13631,
                410,
                -10217,
                3610,
                17795,
                -1843,
                2806,
                -7448,
                990,
                -5476,
                3362,
                -12784,
                18751,
                -150,
                -1694,
                4520,
                -3735,
                -42,
                -10947,
                4229,
                1900,
                -10183,
                -2711,
                19384,
                2997,
                885,
                -16736,
                15628,
                -18820,
                1031,
                -16236,
                3537,
                16036,
                7395,
                -11751,
                -11704,
                -5571,
                -228,
                -18680,
                -13641,
                -4060,
                -10522,
                2862,
                -13057,
                -4004,
                -4448,
                6149,
                5957,
                1975,
                -18140,
                -2303,
                3041,
                13647,
                7449,
                -12267,
                -13189,
                -458,
                14236,
                2805,
                4414,
                -9524,
                -8358,
                -18135,
                -17861,
                8910,
                -16941,
                -16906,
                13781,
                -12920,
                12807,
                7068,
                -560,
                18255,
                3982,
                19253,
                3047,
                -16066,
                -15114,
                -18955,
                -19092,
                -15186,
                15501,
                -12156,
                16511,
                -8667,
                -7412,
                16398,
                -588,
                8523,
                -4784,
                -1313,
                19894,
                698,
                16900,
                -3040,
                10637,
                -9949,
                1505,
                -15844,
                13781,
                11138,
                7490,
                3129,
                5632,
                8807,
                -8268,
                -5399,
                16169,
                1173,
                12380,
                -1448,
                448,
                -19758,
                7169,
                -4058,
                -4111,
                6603,
                -10727,
                -134,
                -8465,
                -1656,
                4674,
                11298,
                -19292,
                10893,
                856,
                -11041,
                17917,
                -5405,
                17353,
                -18501,
                -19417,
                -4804,
                2438,
                -7815,
                -1708,
                6083,
                10211,
                18756,
                10694,
                -19767,
                16763,
                10200,
                -6934,
                -18918,
                886,
                2307,
                -11491,
                13302,
                8141,
                13540,
                15640,
                19987,
                4128,
                15182,
                19884,
                -13905,
                -1239,
                10638,
                -15912,
                -14714,
                -8138,
                -12772,
                -1917,
                4468,
                -16632,
                2437,
                1087,
                5181,
                -13468,
                10004,
                -17418,
                -16725,
                16399,
                1684,
                11118,
                4497,
                10108,
                -14263,
                -5924,
                -15695,
                4035,
                -4675,
                -19370,
                -19509,
                -1146,
                7231,
                -10985,
                7771,
                -4487,
                2465,
                -15313,
                15740,
                11421,
                12077,
                12173,
                -9232,
                -5934,
                1829,
                4092,
                2103,
                -588,
                6107,
                -13938,
                -10791,
                -17463,
                15363,
                -10718,
                -3161,
                10443,
                -3207,
                -9182,
                -14776,
                15279,
                10516,
                -7171,
                5281,
                9477,
                -9093,
                486,
                -377,
                -9146,
                15735,
                14501,
                6830,
                16479,
                -1588,
                -453,
                -13893,
                14026,
                9115,
                19150,
                -15058,
                -1786,
                -15499,
                -6902,
                -12710,
                -1138,
                13648,
                -5341,
                -17072,
                13333,
                10616,
                -4700,
                -5519,
                -18651,
                -15796,
                -1184,
                17604,
                -18757,
                -3919,
                15267,
                -1842,
                10300,
                -2868,
                -4180,
                -18166,
                -2704,
                -5073,
                -8912,
                -15130,
                14127,
                2353,
                -19155,
                -1537,
                19291,
                -766,
                -6726,
                -13762,
                2527,
                -10363,
                17627,
                -18180,
                -9457,
                -14295,
                -2064,
                1289,
                14213,
                -14234,
                7517,
                9670,
                12033,
                -15742,
                13617,
                -16462,
                -16353,
                19504,
                19914,
                12028,
                -8517,
                19374,
                -16347,
                16008,
                -1672,
                9859,
                16192,
                12471,
                -9271,
                -9408,
                15797,
                6478,
                -12447,
                17505,
                -7453,
                -167,
                -6158,
                -8083,
                -4410,
                3947,
                6221,
                4584,
                -11747,
                7853,
                18218,
                -5179,
                8962,
                10499,
                14641,
                -17715,
                16619,
                -17955,
                8641,
                -13138,
                -9904,
                -4175,
                14997,
                -3859,
                -19817,
                -12231,
                15308,
                -13230,
                -5920,
                19186,
                19625,
                -16910,
                9226,
                -19099,
                2049,
                599,
                1909,
                -17160,
                1747,
                -3755,
                -1704,
                5624,
                -3919,
                8068,
                -16400,
                3604,
                11662,
                -15352,
                -12502,
                10874,
                10797,
                657,
                9683,
                6397,
                4080,
                2301,
                -11891,
                -16255,
                -17164,
                16414,
                -12208,
                -5650,
                -9809,
                1517,
                13572,
                -1177,
                -7732,
                11792,
                5627,
                -13243,
                2928,
                -18252,
                -3291,
                13087,
                -10835,
                3973,
                3129,
                11613,
                -8564,
                -9277,
                13748,
                -15793,
                2068,
                10892,
                5988,
                -5277,
                -19774,
                16697,
                11312,
                -18841,
                -11410,
                -2760,
                18671,
                11296,
                -17029,
                -17124,
                13288,
                -17520,
                -8726,
                8512,
                12398,
                -4981,
                18539,
                -3973,
                9851,
                -9116,
                15360,
                -12186,
                7307,
                -12882,
                -17992,
                4139,
                -165,
                -11506,
                8613,
                -5289,
                -9556,
                2947,
                16627,
                621,
                1977,
                -11845,
                13611,
                -9270,
                17961,
                -11477,
                14610,
                13162,
                15381,
                8773,
                -13061,
                6352,
                -1548,
                5559,
                16370,
                -15260,
                6903,
                -6666,
                9829,
                -18315,
                14919,
                -17220,
                3108,
                -2972,
                10352,
                1489,
                12334,
                -5473,
                -17342,
                -14800,
                2595,
                -2003,
                19512,
                -16929,
                16201,
                -11629,
                15963,
                7311,
                -15236,
                12061,
                -16662,
                -15474,
                2960,
                -17516,
                17830,
                -12420,
                -7706,
                7534,
                5235,
                19138,
                -9005,
                4618,
                -7947,
                17301,
                -5093,
                7546,
                -6589,
                -5481,
                19994,
                -15823,
                -13523,
                -18552,
                -13963,
                766,
                -5353,
                6785,
                4276,
                4701,
                8366,
                9288,
                -17673,
                -17195,
                -18493,
                14860,
                -5428,
                -6719,
                -2011,
                9700,
                12551,
                12575,
                10779,
                -10722,
                -16362,
                -8089,
                18011,
                -17308,
                -12083,
                17604,
                -6572,
                -17401,
                10213,
                14163,
                18514,
                -17687,
                -18712,
                10985,
                2052,
                17733,
                14730,
                -1711,
                9533,
                14359,
                -9692,
                5079,
                -1162,
                9431,
                -4389,
                -2217,
                14274,
                16008,
                -18615,
                18692,
                -6784,
                7257,
                19462,
                -10665,
                9212,
                -4272,
                6895,
                -13211,
                -17097,
                9470,
                5725,
                -11569,
                -415,
                -928,
                -18397,
                -10124,
                -15710,
                3566,
                -8022,
                -9262,
                -13460,
                1059,
                4681,
                -7536,
                -17869,
                463,
                7143,
                8860,
                220,
                5567,
                -15520,
                973,
                -16197,
                12513,
                -3203,
                -17194,
                -18816,
                -13616,
                -9542,
                -11818,
                7450,
                19994,
                -13407,
                19679,
                789,
                -3823,
                6686,
                -14096,
                -16957,
                -14558,
                13684,
                13995,
                21,
                -3372,
                -13536,
                1118,
                15040,
                -16177,
                -4731,
                6094,
                -13836,
                -10101,
                14428,
                15756,
                2789,
                -5357,
                -12012,
                19191,
                18593,
                11459,
                7590,
                -7810,
                -941,
                18109,
                1953,
                -4363,
                5846,
                -10655,
                17006,
                6241,
                5600,
                12580,
                -13347,
                -14281,
                -4432,
                -2760,
                6220,
                -5278,
                -19866,
                14679,
                10291,
                -3072,
                18555,
                6287,
                -4439,
                13884,
                -16744,
                13028,
                2073,
                -10635,
                -17018,
                5076,
                -11208,
                -18730,
                -15496,
                -9279,
                7056,
                -18209,
                6819,
                8072,
                4973,
                19805,
                -6014,
                -11026,
                7809,
                2642,
                -8671,
                -10501,
                -12278,
                18375,
                8572,
                9527,
                19918,
                8063,
                10897,
                9076,
                12485,
                15627,
                18809,
                7300,
                -5119,
                -3941,
                -7584,
                3465,
                7640,
                14982,
                -16947,
                -11462,
                -19163,
                14489,
                3691,
                -4248,
                3433,
                17214,
                5111,
                539,
                9561,
                -6788,
                -18072,
                2315,
                4519,
                -6873,
                7278,
                -3422,
                8450,
                -16974,
                -428,
                13986,
                -15469,
                15125,
                -4945,
                -3890,
                1358,
                -8462,
                -4682,
                -6879,
                -15188,
                -11032,
                18697,
                -2932,
                -18045,
                -6192,
                -17037,
                4913,
                -7255,
                -7766,
                6947,
                7923,
                16112,
                719,
                5050,
                -12963,
                15484,
                -17422,
                -17110,
                -16427,
                -9754,
                19715,
                1078,
                -18462,
                2286,
                13530,
                18040,
                -6124,
                -3794,
                16083,
                -3548,
                -18406,
                15369,
                -4193,
                12427,
                1047,
                1254,
                -17257,
                -12767,
                609,
                16964,
                12212,
                -3943,
                6755,
                15479,
                -11785,
                5187,
                -541,
                -18911,
                -14607,
                8832,
                -7162,
                -18108,
                -1929,
                -11272,
                -11514,
                -7006,
                -14670,
                8962,
                1197,
                -14728,
                304,
                3784,
                -19021,
                1218,
                8657,
                -10176,
                -4167,
                15554,
                -2605,
                18940,
                -878,
                13450,
                11921,
                2643,
                5596,
                -852,
                -3199,
                -19836,
                -881,
                8024,
                -6405,
                1549,
                12878,
                1283,
                17238,
                -14540,
                -5104,
                1673,
                -5868,
                9028,
                -17168,
                -6331,
                13204,
                -18456,
                -491,
                -15641,
                -15461,
                11735,
                -298,
                18071,
                10544,
                -4218,
                11621,
                13081,
                -19099,
                -10454,
                16680,
                -1046,
                939,
                14256,
                11790,
                7560,
                16934,
                3983,
                -15690,
                185,
                -1927,
                -5782,
                2846,
                -8244,
                -19065,
                -14135,
                13118,
                -2041,
                -11442,
                19834,
                -7292,
                16662,
                -13806,
                -19404,
                -8793,
                3713,
                -10685,
                2999,
                -18157,
                -15387,
                5790,
                -5180,
                -11785,
                2253,
                -14048,
                -2227,
                -12499,
                -6500,
                2892,
                -15058,
                3253,
                -4590,
                16847,
                6273,
                -9968,
                -7114,
                -125,
                -1909,
                -9777,
                1326,
                -13201,
                -4206,
                -13720,
                14198,
                -17287,
                -7610,
                9812,
                5113,
                19378,
                3097,
                4968,
                -1402,
                -1556,
                8867,
                12701,
                2485,
                5146,
                -7801,
                1702,
                4013,
                -416,
                -5331,
                19442,
                -19221,
                1992,
                4273,
                -4725,
                5936,
                -12649,
                -11662,
                -5765,
                2405,
                9412,
                16843,
                13441,
                -8081,
                -3835,
                18424,
                -18660,
                2453,
                13606,
                -9685,
                17407,
                -4968,
                11789,
                1623,
                -5351,
                -10617,
                9795,
                8101,
                3364,
                -13792,
                -10369,
                15850,
                -15835,
                14633,
                8694,
                6917,
                -4623,
                8170,
                -17025,
                -2267,
                19542,
                9961,
                6913,
                15204,
                -1900,
                2965,
                -4173,
                16364,
                16222,
                8509,
                -2667,
                -12561,
                18823,
                724,
                8719,
                -15851,
                -17774,
                12254,
                -13242,
                -4322,
                13202,
                14598,
                17339,
                8156,
                11835,
                -8527,
                -14215,
                981,
                -16428,
                7900,
                18069,
                2175,
                -3541,
                -218,
                -465,
                -18561,
                15687,
                5454,
                13072,
                9367,
                -14519,
                1198,
                -4891,
                11152,
                4186,
                8587,
                958,
                14339,
                -13779,
                -8804,
                15808,
                -4268,
                -15531,
                -9947,
                -4916,
                17980,
                18454,
                -10340,
                -10381,
                -17312,
                -15628,
                -12121,
                8441,
                576,
                13804,
                -12242,
                -3611,
                -18884,
                17287,
                -7116,
                -17202,
                -14520,
                2043,
                7679,
                -16896,
                1212,
                9601,
                -11022,
                6721,
                8612,
                5706,
                -6430,
                -12435,
                10969,
                8932,
                -15291,
                -7995,
                144,
                12576,
                -10494,
                -9746,
                -8016,
                4549,
                -14966,
                781,
                -10625,
                2117,
                -14577,
                -6308,
                1078,
                -17034,
                19779,
                3281,
                -10806,
                -2959,
                10670,
                14877,
                -16548,
                -2628,
                -7124,
                12610,
                18980,
                -6520,
                7749,
                16275,
                -4558,
                -19951,
                -3657,
                -12490,
                -10206,
                -4403,
                -19098,
                -29,
                -19138,
                -4638,
                12435,
                18323,
                11382,
                -17282,
                -8142,
                12328,
                -1670,
                9019,
                16944,
                -18859,
                4254,
                12083,
                -251,
                7081,
                10356,
                -2904,
                2737,
                19487,
                -10427,
                -8425,
                -4040,
                5587,
                6783,
                -11470,
                10161,
                -15016,
                13321,
                -9392,
                12221,
                -836,
                2842,
                -10623,
                -5445,
                -7626,
                -10702,
                13052,
                1008,
                -175,
                153,
                457,
                4534,
                5445,
                19157,
                9135,
                7170,
                14336,
                15399,
                -16760,
                -7796,
                19350,
                13900,
                15629,
                -14040,
                6148,
                6128,
                18875,
                11915,
                11475,
                12886,
                12521,
                -11181,
                3763,
                -17558,
                17919,
                17041,
                -5845,
                -12305,
                4692,
                10070,
                438,
                -15011,
                -19987,
                -7123,
                -14656,
                2266,
                -16661,
                15734,
                -18988,
                -10173,
                -13865,
                -12268,
                -4666,
                19902,
                -16105,
                -4686,
                -17380,
                -18893,
                -10438,
                6377,
                -1147,
                -13780,
                -18334,
                14300,
                -12197,
                15656,
                -17571,
                -15965,
                540,
                -2234,
                517,
                -17832,
                3597,
                -19799,
                16383,
                -17155,
                307,
                86,
                -4644,
                16525,
                -8460,
                -4762,
                19712,
                235,
                7892,
                2408,
                -17555,
                19261,
                -13404,
                12608,
                11441,
                -5004,
                -1641,
                -5711,
                17764,
                -12750,
                -4153,
                17965,
                9358,
                9806,
                -4816,
                -12708,
                -1562,
                7677,
                15706,
                -510,
                18905,
                -1801,
                9312,
                -14054,
                2116,
                -11354,
                -15244,
                -666,
                3807,
                2924,
                17073,
                -16741,
                -5927,
                -1791,
                9108,
                -14900,
                3700,
                -1936,
                13850,
                800,
                15024,
                -10071,
                -37,
                5224,
                -9693,
                13279,
                -18393,
                -13887,
                -5336,
                -6057,
                -11000,
                -13835,
                9298,
                8389,
                -18953,
                -15935,
                15886,
                -10232,
                -14567,
                -4560,
                -17180,
                -5223,
                -2896,
                -13328,
                -8650,
                -8166,
                -9336,
                15354,
                16790,
                -333,
                3328,
                2990,
                -5637,
                -9595,
                11882,
                19081,
                6092,
                2114,
                -14908,
                -16905,
                5436,
                -19664,
                -15365,
                7508,
                8463,
                19431,
                359,
                3276,
                -14522,
                -12861,
                -11818,
                4699,
                2368,
                -3557,
                -4477,
                -15504,
                -14562,
                -766,
                15790,
                -2628,
                1541,
                -2731,
                15155,
                -4629,
                19167,
                -18515,
                -18940,
                5009,
                -14583,
                10193,
                -19797,
                11575,
                12483,
                -18579,
                -3478,
                16882,
                -5377,
                -8846,
                3373,
                -8651,
                -8833,
                -11572,
                13982,
                -4442,
                4322,
                -10520,
                -17052,
                -17159,
                2207,
                -9989,
                -9986,
                -9175,
                -7168,
                -7452,
                9322,
                18902,
                -4215,
                16299,
                -13263,
                388,
                15223,
                17325,
                10404,
                -15914,
                -10945,
                -7029,
                -13587,
                -8655,
                9167,
                10055,
                649,
                8511,
                7816,
                -7347,
                -8570,
                -12508,
                -1454,
                15812,
                -5988,
                -5518,
                -6517,
                8521,
                -10879,
                15276,
                -18958,
                4778,
                4273,
                3246,
                -8730,
                -15378,
                18836,
                1714,
                -17783,
                16950,
                -10183,
                -7886,
                -5576,
                11536,
                3076,
                -17241,
                -10595,
                -8483,
                -19853,
                2569,
                -5341,
                2198,
                -13403,
                -5756,
                206,
                6604,
                7639,
                -12441,
                10124,
                6368,
                16313,
                17852,
                -7014,
                -1863,
                -9302,
                5340,
                -12243,
                -5072,
                7175,
                19848,
                -6342,
                -15264,
                9020,
                15591,
                7792,
                7796,
                -689,
                -6034,
                -2516,
                3411,
                14224,
                -10459,
                5931,
                -5294,
                -9188,
                12273,
                -13,
                8096,
                -6570,
                8062,
                -15155,
                2995,
                1330,
                -8626,
                234,
                16507,
                13032,
                -8849,
                19263,
                3227,
                -15813,
                -17772,
                6203,
                -2739,
                2707,
                8601,
                -17085
    }));
    }
}
